<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /**
         * 一般的语言实现链表都需要指针来实现
         * 而js的引用类型本来就是按值引用的
         * 变量中保存的实质上是一个指向其对应对象的一个指针
         */
        class Node {
            constructor(val) {
                this.val = val;
                this.next = null;
            }
        }
        class LinkedList {  //传入和返回都是Node类型，第一个元素下标0
            constructor(node) {
                this.head = node;
                this.length = 1;
            }
            get isEmpty() {
                return !this.length;
            }
            append(node) {
                var lastNode = this.findAsIndex(this.length - 1);
                lastNode.next = node;
                this.length++;
            }
            insert(index, node) {   //在哪个元素之前插入
                var targetNode = this.findAsIndex(index - 1);
                node.next = targetNode.next;
                targetNode.next = node;
                this.length++
            }
            remove(index) {
                var preNode = this.findAsIndex(index - 1);
                var nextNode = this.findAsIndex(index + 1);
                preNode.next = nextNode;
            }
            findAsIndex(index) {
                if (index > this.length) {
                    console.log('越界');
                    return
                }
                if (index === 0) {
                    return this.head;
                }
                var curNode = this.head;  //浅拷贝 所以curNode的值改变也能改变head的值
                while (index && curNode) {
                    index--;
                    curNode = curNode.next;
                }
                return curNode;
            }
            toString() {
                var curNode = this.head;
                var arr = [];
                var i = 0;
                while (curNode) {
                    arr[i++] = curNode.val;
                    curNode = curNode.next;
                }
                return arr.toString();
            }
            //实现链表的翻转 
            //一种方法是定义一个新数组 将链表的值存入数组 然后用该数组逆序生成链表 这种方法不推荐
            //一般面试时候用以下这种在原来链表的基础上（即不开辟新空间） 实现链表的翻转比较加分
            reverse(head) {
                var list = head
                var p = list
                var q = null
                if (!head) {
                    return null
                }
                while (p.next !== null) {
                    q = p.next
                    p.next = q.next
                    q.next = list
                    list = q
                }
                return list
            }
            //根据值查找结点
            findIndex(element) {
                var current = this.head
                var index = 1
                if (current === null) {
                    return null
                }
                while (current.val !== element) {
                    current = current.next
                    index++
                    if (index > this.length) {
                        return false
                    }
                }
                return current
            }
            //判断链表是否有环
            //第一种方法是哈希表法
            //第二种方法是访问标记法
            //第三种是快慢指针法
            Judge(node) {
                var fast = node.next.next
                console.log(fast)
                var slow = node.next
                while (node) {
                    if (fast === slow) {
                        console.log('存在环')
                        return true
                    }
                    if (fast === null) {
                        return false
                    }
                    fast = fast.next.next
                    slow = slow.next
                }

            }
        }
        let list = new LinkedList(new Node('1'));
        list.append(new Node('2'));
        list.append(new Node('2'));
        list.append(new Node('3'));
        list.append(new Node('5'));
        console.log(list.head)
    </script>
</body>

</html>